You are given positions of N cities situated on X axis. The position of the ith city is denoted by array value Location[i].You have a bike which can travel atmost K unit distance once the tank is full and each city has a fuel pump. You can assume that once the bike reaches a city its tank is again filled up completely.Now you have to answer Q queries where each query is of the following form.
Constraints:
Note :- Use fast i/o.
Format of the input file:
First line : T i.e Number of testcases.
For each testcase :
First line : Three space separated integers N , K and Q.
Second line : N space separated integers denoting the location of cities .
Next Q lines : Three space separated LRX integers denoting the query.
Format of the output file:
Output the answer to each query in a separate line.
For second query you can reach all the cities from city with location 3(index 2) except the city with location 9(index 4) that lie in the range [1,5] of the array location[i]. Note that X , L and R are indexes of the array.